1. Field of the Invention
The present invention relates to telecommunications systems and, in particular, to an adaptive filtering coefficient update technique that combines features of the least mean squares algorithm and the sign algorithm to arrive at a hybrid stochastic gradient algorithm that is both fast and consistently convergent.
2. Discussion of the Prior Art
Two common adaptive filtering coefficient update algorithms are the Least Mean Squares (LMS) and the Sign Algorithm (SA). The LMS method is not consistently successful in converging a filter. However, in those situations where it does operate successfully, it is fast. The SA method, on the other hand, always succeeds, but it is slow.
A typical adaptive filtering application, shown in FIG. 1, involves driving a channel with an unknown impulse response H, EQU H'=(h.sub.0, h.sub.1,...,h.sub.m) (1)
where the ' character denotes transposition, with a known input signal S(n), EQU S'(n)=(s(n), s(n-1),..,s(n-m)) (2)
The output of the channel at time n is given by the convolution sum, ##EQU2##
In adaptively tracking the channel output, the adaptive filter produces an output x(n), EQU x(n)=S'(n) A(n) (4)
where EQU A'(n)=(a.sub.0 (n), a.sub.1 (n),.., a.sub.m (n)) (5)
is the adaptive filter impulse response at time n.
Being time variable, the adaptive filter coefficients are updated as follows, EQU A(n+1)=A(n)+g(n) f.sub.1 (e(n)) f.sub.2 (S(n)) (6) EQU e(n)=y(n)-x(n) (7)
where e(n) is the prediction error, g(n) is a gain that can be either constant or time variable, and f.sub.1 (.) and f.sub.2 (.) are generalized functions.
Adhering to adaptive filtering terminology, it is said that "convergence" is achieved when EQU A(n)=H for all n, (8) EQU e(n)=Q for all n, (9)
In practice, Equations (8) and (9) above will not be exact equalities. Rather, there will be a misadjustment between A(n) and H, and 0&lt;.vertline.e(n).vertline.&lt;.rho., where .rho. is small, i.e. the practical limit of the algorithm.
Both the Least Mean Squares algorithm and the Sign Algorithm have received extensive treatment in the theoretical literature and have found wide practical application.
Referring to FIG. 2, which shows a possible circuit implementation of the LMS algorithm, the LMS algorithm structure may be expressed as follows: EQU A(n+1)=A(n)+K e(n) S(n) (10)
where K is a constant positive coefficient adaption step size. The choice of K for an assured convergence is discussed by B. Widrow et al., "Stationary and Non-Stationary Learning Characteristics of the LMS Adaptive Filter", Proceedings of the IEEE, vol. 64, pp. 1151-1162, Aug. 1976.
If K is chosen according to the criteria set forth by Widrow et al, then convergence is assured. However, in practical telecommunications applications, the channel H over which echo cancellation or equalization is being performed is not known. Consequently, it is impossible to determine K a priori, and convergence is not guaranteed over any arbitrary channel. When convergence does take place, the result is the minimization of the expected value of the error squared u=E(e(n).sup.2); that is, the error variance is minimized. The product e(n)S(n) used in Eq. (10) above is a biased estimate of the slope of the expected value of the error squared w=dv/dA(n).
In a digital implementation of the LMS algorithm, when convergence starts, e(n) is large and K is typically fixed at K=1/(2.sup.11); the coefficients A(n) are 24 bits wide (1 sign bit+23 magnitude bits). The product p=Ke(n) is equivalent to shifting e(n) to the right by 11 places and, initially, when e(n) is large, p is still on average such that .vertline.p.vertline.&gt;1/(2.sup.23) and, therefore, this update is "seen" by A(n). However, as convergence progresses and e(n) becomes smaller as desired, .vertline.p.vertline.&lt;1/(2.sup.23) and the coefficients A(n) are not being updated anymore. Therefore, convergence is not optimal, since by using more than 24 bits for A(n), convergence could have proceeded and e(n) could have been further decreased.
The LMS algorithm has also shown parameter drift properties that are described by Sethares et al, "Parameter Drift in LMS Adaptive Filters", IEEE Transactions on Acoustics, Speech and Signal Processing, vol.ASSP-34 No. 4, Aug. 1986, and have been observed in a working prototype. The problem is that, with bounded steady state inputs, the output x(n) and the error e(n) remain bounded and approximately zero, respectively, while the parameters A(n) drift away from H very slowly.
Referring to FIG. 3, which shows a possible circuit implementation of the Sign Algorithm, the Sign Algorithm structure may be expressed as follows: EQU A(n+1)=A(n)+L sign(e(n)) S(n) (11)
where L is a constant positive step size, usually equal to the least significant bit in the coefficients A(n). Convergence is achieved for any positive L, as discussed by A. Gersho, "Adaptive Filtering With Binary Reinforcement", IEEE Transactions on Information Theory, Vol. IT-30, No. 2, Mar. 1984.
For the same desired residual error variance as the LMS technique described above, the convergence time for the Sign Algorithm is always longer than the LMS algorithm, as described by Gersho and by T.A.C.M. Claasen and W.F.G. Mecklenbrauker, "Comparison of the Convergence of Two Algorithms for Adaptive FIR Digital Filters", IEEE Transactions on Circuits and Systems, Vol. CAS-28, No. 6, June 1981. Implementation of the Sign Algorithm is simpler than the LMS algorithm, since p=Ke(n) in LMS becomes +L or -L in the Sign Algorithm. When convergence is achieved, the Sign Algorithm minimizes the expectation of the absolute value of the error, E(.vertline.e(n).vertline.). In the course of convergence and after it is achieved, in a digital implementation, the coefficient vectors A(n) always "see" the updating increment, since to every coefficient of A(n), a least significant bit is added or subtracted depending on sign(e(n)) and the corresponding s(n-j).
No parameter drift has been observed in the Sign Algorithm. A theoretical reason is not known, but it is believed that the hard limiting of the error signal gives an unbiased estimate of w=dv/dA(n), which is essential for the stability of the steady state convergence.